package everyday.leetcode.editor.cn;

import com.dq.utils.CreateArray;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/2  21:22
 * @Description: 304. 二维区域和检索 - 矩阵不可变
 */
public class RangeSumQuery2DImmutable {
    public static void main(String[] args) {
        int[][] matrix = {{-4,-5}};
        NumMatrix numMatrix = new RangeSumQuery2DImmutable().new NumMatrix(matrix);
        System.out.println(numMatrix.sumRegion(0,0,0,0));
        System.out.println(numMatrix.sumRegion(0,0,0,1));
        System.out.println(numMatrix.sumRegion(0,1,0,1));
    }
    class NumMatrix {

        private int[][] sums = null;

        public NumMatrix(int[][] matrix) {

            if(matrix==null || matrix.length==0) return;
            sums = new int[matrix.length][matrix[0].length];
            sums[0][0] = matrix[0][0];
            System.out.println(matrix.length + " " + matrix[0].length);
            for(int i = 1; i < matrix.length; i++){
                sums[i][0] = sums[i-1][0] + matrix[i][0];
                System.out.println("e");
            }
//            for (int i = 0; i < sums.length; i++) {
//                System.out.println(Arrays.toString(sums[i]));;
//            }
            for(int i = 1; i < matrix[0].length; i++){
                sums[0][i] = sums[0][i-1] + matrix[0][i];
                System.out.println("e1");
            }
            for(int i = 1; i < matrix.length; i++){
                for(int j = 1; j < matrix[0].length; j++){
                    sums[i][j] = sums[i-1][j] + ( sums[i][j-1] - sums[i-1][j-1] ) + matrix[i][j];
                    System.out.println("e2");
                }
            }

        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            if(row1==0 && col1==0) return sums[row2][col2];
            if(row1==0) return sums[row2][col2] - sums[row2][col1-1];
            if(col1==0) return sums[row2][col2] - sums[row1-1][col2];

            return sums[row2][col2] - sumRegion(0,0, row1-1,col2) - sumRegion(row1,0, row2, col1-1);
        }
    }

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
}
